/*
https://leetcode.cn/problems/satisfiability-of-equality-equations/description/
990.等式方程的可满足性
方钊堉 2024.10.13
并查集
*/


class Solution {

    struct UnionFind {
        int labels[26]; // 存储每个字母的标签（父节点）

        // 查找函数，带路径压缩优化
        int find(int x) {
            if (x == labels[x]) {
                return x;
            } else {
                return find(labels[x]);
            }
        }

        // 合并两个节点所在的集合
        void unionNodes(int x, int y) {
            labels[find(x)] = find(y);
        }
    };

public:
    // 判断方程是否可能成立
    bool equationsPossible(vector<string>& equations) {
        // 按等号优先排序方程
        sort(equations.begin(), equations.end(), [](const string &a, const string &b) {
            if (a[1] != b[1]) {
                return a[1] == '='; // 等号优先
            } else {
                return a < b; // 字典序排序
            }
        });

        UnionFind uni;
        // 初始化并查集
        for (int i = 0; i < 26; ++i) {
            uni.labels[i] = i;
        }

        // 处理每个方程
        for (auto &eq : equations) {
            char a = eq[0];
            char b = eq[3];

            if (eq[1] == '=') {
                // 处理相等方程
                if (a != b) {
                    uni.unionNodes(a - 'a', b - 'a');
                }
            } else {
                // 处理不等方程
                if (a == b) {
                    return false; // 相同字符不能不相等
                }
                int x = uni.find(a - 'a');
                int y = uni.find(b - 'a');
                if (x == y) {
                    return false; // 如果两个字符在同一个集合中，则不等方程不成立
                }
            }
        }

        return true;
    }
};